#include <iostream>
#include <string>
#include <string.h>
using namespace std;
typedef unsigned short ushort;
ushort RAM[1000][3];
ushort REG[10]; 
#define clear_register() memset(REG,0, 20);
#define init_ram() memset(RAM , 0, 6000);
#define INS(i) RAM[i][0]
#define ARG1(i) RAM[i][1]
#define ARG2(i) RAM[i][2]

void load_ram() {
	ushort pc = 0;
	string statement("");
	cin >> noskipws;
	getline(cin, statement);
	while(statement.size() < 3)
		getline(cin, statement);
	while(cin.eof() == false) {
		RAM[pc][0] = statement[0]-48;
		RAM[pc][1] = statement[1]-48;
		RAM[pc][2] = statement[2]-48;
		getline(cin, statement);
		if(statement.size() < 3)
			break;
		pc++;
	}
}

void print_ram() {
	for(ushort i = 0; i < 1000; i++) {
		cout << RAM[i][0] << RAM[i][1] << RAM[i][2] << endl;
	}
}

/* 100 means halt
   2dn means set register d to n (between 0 and 9)
   3dn means add n to register d
   4dn means multiply register d by n
   5ds means set register d to the value of register s
   6ds means add the value of register s to register d
   7ds means multiply register d by the value of register s
   8da means set register d to the value in RAM whose address is in register a
   9sa means set the value in RAM whose address is in register a to the value of register s
   0ds means goto the location in register d unless register s contains 0
   */

ushort execute ( ushort pc) {
	ushort counter = 0;
	while( true ) {
		switch(INS(pc)) {
			case 0:
				REG[ARG2(pc)] != 0 ? pc = REG[ARG1(pc)] : pc++;	
				counter +=1;
				break;
			case 1:
				counter +=1;
				goto DONE;
				break;
			case 2:
				REG[ARG1(pc)] = ARG2(pc);
				pc++;
				counter += 1;
				break;
			case 3:
				REG[ARG1(pc)] = (REG[ARG1(pc)] + ARG2(pc)) % 1000;
				pc++;
				counter += 1;
				break;
			case 4:
				REG[ARG1(pc)] = (REG[ARG1(pc)] * ARG2(pc)) % 1000;
				pc++;
				counter += 1;
				break;
			case 5:
				REG[ARG1(pc)] = REG[ARG2(pc)];
				pc++;
				counter += 1;
				break;
			case 6:
				REG[ARG1(pc)] = (REG[ARG1(pc)] + REG[ARG2(pc)]) % 1000;
				pc++;
				counter += 1;
				break;
			case 7:
				REG[ARG1(pc)] = (REG[ARG1(pc)] * REG[ARG2(pc)]) % 1000;
				pc++;
				counter += 1;
				break;
			case 8:
				REG[ARG1(pc)] =   RAM[REG[ARG2(pc)]][2]+\
								 (RAM[REG[ARG2(pc)]][1] << 3) +\
								 (RAM[REG[ARG2(pc)]][1] << 1)+ \
								 (RAM[REG[ARG2(pc)]][0] << 6) +\
								 (RAM[REG[ARG2(pc)]][0] << 5) + \
								 (RAM[REG[ARG2(pc)]][0] << 2);
				pc++;
				counter += 1;
				break;
			case 9:
				RAM[REG[ARG2(pc)]][2] = REG[ARG1(pc)]%10;
				RAM[REG[ARG2(pc)]][1] = (REG[ARG1(pc)]/10)%10;
				RAM[REG[ARG2(pc)]][0] = REG[ARG1(pc)]/100;
				pc++;
				counter += 1;
				break;
			default:
				break;
		}
		pc %= 1000;
	}
DONE:
	return counter;
}

/* main
 *  * */
int main() {
	long no_of_programmes = 0;
	cin >> no_of_programmes;
	cin.ignore(); // changeLine
	while ( no_of_programmes > 0 ) {
		clear_register();
		init_ram();
		load_ram();
		//print_ram();
		cout << execute(0) <<endl;
		if(no_of_programmes > 1)
			cout << endl;
		no_of_programmes--;
	}
	return 0;
}
